package ch09_06;

public class Solution {
    public static void printAllParentheses(int n) {
	char[] arr = new char[n << 1];
	long[] count = {0};
	genParentheses(arr, n, n, 0, count);
    }

    private static void genParentheses(char[] arr, int l, int r, int index, long[] count) {
	if (index == arr.length) {
		count[0]++;
		System.out.print(count[0] + ":\t");
	    System.out.println(arr);
	    return;
	}
	if (l > 0) {
	    arr[index] = '(';
	    genParentheses(arr, l - 1, r, index + 1, count);
	}
	if (r > l) {
	    arr[index] = ')';
	    genParentheses(arr, l, r - 1, index + 1, count);
	}
    }

    public static void main(String... args) {
	int n = 15;
	printAllParentheses(n);
    }
}